package com.chj.gaoji.class09;

public class Code04_MaximumSumof3NonOverlappingSubarrays {

	public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
		int N = nums.length;
		int[] range = new int[N];
		int[] left = new int[N];
		int sum = 0;
		for (int i = 0; i < k; i++) {
			sum += nums[i];
		}
		range[0] = sum;
		left[k - 1] = 0;
		int max = sum;
		for (int i = k; i < N; i++) {
			sum = sum - nums[i - k] + nums[i];
			range[i - k + 1] = sum;
			left[i] = left[i - 1];
			if (sum > max) {
				max = sum;
				left[i] = i - k + 1;
			}
		}
		sum = 0;
		for (int i = N - 1; i >= N - k; i--) {
			sum += nums[i];
		}
		max = sum;
		int[] right = new int[N];
		right[N - k] = N - k;
		for (int i = N - k - 1; i >= 0; i--) {
			sum = sum - nums[i + k] + nums[i];
			right[i] = right[i + 1];
			if (sum >= max) {
				max = sum;
				right[i] = i;
			}
		}
		int a = 0;
		int b = 0;
		int c = 0;
		max = 0;
		for (int i = k; i < N - 2 * k + 1; i++) {
			int part1 = range[left[i - 1]];
			int part2 = range[i];
			int part3 = range[right[i + k]];
			if (part1 + part2 + part3 > max) {
				max = part1 + part2 + part3;
				a = left[i - 1];
				b = i;
				c = right[i + k];
			}
		}
		return new int[] { a, b, c };
	}

	public static int[] maxSumOfThreeSubarrays02(int[] nums, int k) {
		int N = nums.length;
		int[] range = new int[N + 1];
		int[][] left = new int[N][k + 1];
		int[][] right = new int[N][k + 1];
		int[] preSum = new int[N + 1];
		preSum[0] = 0;
		for (int i = 1; i < preSum.length; i++) {
			preSum[i] = preSum[i - 1] + nums[i - 1];
		}

		range[0] = 0;
		for (int i = 1; i < range.length; i++) {
			if ((i + k - 1) >= preSum.length) {
				continue;
			}
			range[i] = preSum[i + k - 1] - preSum[i - 1];
		}

		int max = preSum[k];
		left[k - 1][k] = 0;
		for (int i = k; i < N; i++) {
			left[i][k] = left[i - 1][k];
			int temp = preSum[i + 1] - preSum[i - k + 1];
			if (temp > max) {
				max = temp;
				left[i][k] = i - k + 1;
			}

		}

		int[] tailSum = new int[N + 1];
		tailSum[N] = 0;
		for (int i = N - 1; i >= 0; i--) {
			tailSum[i] = tailSum[i + 1] + nums[i];
		}

		max = tailSum[N - k];
		right[N - k][k] = N - k;
		for (int i = N - k - 1; i >= 0; i--) {
			int temp = tailSum[i] - tailSum[i + k];
			if (temp >= max) {
				max = temp;
				right[i][k] = i;
			}
		}

		int a = 0;
		int b = 0;
		int c = 0;
		max = 0;
		for (int i = k; i <= N - 2 * k + 1; i++) {
			int part1 = range[left[i - 1][k] + 1];
			int part2 = range[i + 1];
			int part3 = range[right[i + k][k]];
			if (part1 + part2 + part3 > max) {
				max = part1 + part2 + part3;
				a = left[i - 1][k];
				b = i;
				c = right[i + k][k];
			}
		}
		return new int[] { a, b, c };
	}

	public static void main(String[] args) {
		{
			int[] nums = { 9, 8, 7, 6, 2, 2, 2, 2 };
			int k = 2;
			int[] ans = maxSumOfThreeSubarrays(nums, k);
			System.out.println(ans[0] + "," + ans[1] + "," + ans[2]);
		}

		{
			int[] nums = { 9, 8, 7, 6, 2, 2, 2, 2 };
			int k = 2;
			int[] ans = maxSumOfThreeSubarrays02(nums, k);
			System.out.println(ans[0] + "," + ans[1] + "," + ans[2]);
		}
	}

}
